package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
 * <p>
 * 请你找出并返回只出现一次的那个数。
 * <p>
 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
 * <p>
 * 链接：https://leetcode.cn/problems/single-element-in-a-sorted-array
 * <p>
 * 1 <= nums.length <= 10^5
 * 0 <= nums[i] <= 10^5
 * @version 1.0
 * @date 2022/8/8 14:56
 */
public class singleNonDuplicate {

    public static void main(String[] args) {
        System.out.println(singleNonDuplicate1(new int[]{1, 1, 2}));
    }

    // 思路：a^b^a = b，这种解法更适合无序的数组
    private int singleNonDuplicate(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

    // 思路：二分查找
    private static int singleNonDuplicate1(int[] nums) {
        // [1, 2, 2]
        // [1, 1, 2]
        // [0, 0, 1, 1, 2]
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) return nums[mid];
            // nums.length 是奇数，要保持 right - left + 1 是奇数
            if (nums[mid] == nums[mid - 1]) {
                if ((mid - left + 1) % 2 == 0) {
                    left = mid + 1;
                }else {
                    right = mid;
                }
                continue;
            }
            if (nums[mid] == nums[mid + 1]) {
                if ((right - mid + 1) % 2 == 0) {
                    right = mid - 1;
                }else {
                    left = mid;
                }
            }
        }
        return nums[right];
    }
}
